{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Uncrossed Lines"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxUncrossedLines"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不相交的线"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在两条独立的水平线上按给定的顺序写下 <code>nums1</code> 和 <code>nums2</code> 中的整数。</p>\n",
    "\n",
    "<p>现在，可以绘制一些连接两个数字 <code>nums1[i]</code>&nbsp;和 <code>nums2[j]</code>&nbsp;的直线，这些直线需要同时满足满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>&nbsp;<code>nums1[i] == nums2[j]</code></li>\n",
    "\t<li>且绘制的直线不与任何其他连线（非水平线）相交。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。</p>\n",
    "\n",
    "<p>以这种方法绘制线条，并返回可以绘制的最大连线数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/04/26/142.png\" style=\"width: 400px; height: 286px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = <span id=\"example-input-1-1\">[1,4,2]</span>, nums2 = <span id=\"example-input-1-2\">[1,2,4]</span>\n",
    "<strong>输出：</strong><span id=\"example-output-1\">2</span>\n",
    "<strong>解释：</strong>可以画出两条不交叉的线，如上图所示。 \n",
    "但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。\n",
    "</pre>\n",
    "\n",
    "<div>\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = <span id=\"example-input-2-1\">[2,5,1,2,5]</span>, nums2 = <span id=\"example-input-2-2\">[10,5,2,1,5,2]</span>\n",
    "<strong>输出：</strong><span id=\"example-output-2\">3</span>\n",
    "</pre>\n",
    "\n",
    "<div>\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = <span id=\"example-input-3-1\">[1,3,7,1,7,5]</span>, nums2 = <span id=\"example-input-3-2\">[1,9,2,5,1]</span>\n",
    "<strong>输出：</strong><span id=\"example-output-3\">2</span></pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "</div>\n",
    "</div>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums1.length, nums2.length &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= nums1[i], nums2[j] &lt;= 2000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [uncrossed-lines](https://leetcode.cn/problems/uncrossed-lines/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [uncrossed-lines](https://leetcode.cn/problems/uncrossed-lines/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,4,2]\\n[1,2,4]', '[2,5,1,2,5]\\n[10,5,2,1,5,2]', '[1,3,7,1,7,5]\\n[1,9,2,5,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, a: List[int], b: List[int]) -> int:\n",
    "        n, m = len(a), len(b)\n",
    "\n",
    "        dp = [[0] * (m + 1) for i in range(n + 1)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if a[i] == b[j]:\n",
    "                    dp[i + 1][j + 1] = dp[i][j] + 1\n",
    "                else:\n",
    "                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])\n",
    "        return dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:\n",
    "        dp = [[0] * (len(B) + 1) for i in range(len(A) + 1)]\n",
    "        for i in range(1, len(A) + 1):\n",
    "            for j in range(1, len(B) + 1):\n",
    "                if A[i-1] == B[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:\n",
    "        AN, BN = len(A), len(B)\n",
    "        dp = [[0] * (BN + 1) for _ in range(AN + 1)]\n",
    "        for i in range(AN):\n",
    "            a = A[i]\n",
    "            for j in range(BN):\n",
    "                if B[j] == a:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n",
    "        return dp[AN - 1][BN - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:\n",
    "        #如果A[x]!=B[y]，那么f(x,y)=max(f(x-1,y),f(x,y-1));\n",
    "        #如果A[x]==B[y]，那么f(x,y)=f(x-1,y-1)+1;\n",
    "        x=len(A)\n",
    "        y=len(B)\n",
    "        res=[[0]*(y+1) for i in range(x+1)]\n",
    "        for i,a in enumerate(A):\n",
    "            for j,b in enumerate(B):\n",
    "                \n",
    "                if a==b:\n",
    "                    res[i+1][j+1]=res[i][j]+1\n",
    "                else:\n",
    "                    res[i+1][j+1]=max(res[i][j+1],res[i+1][j])\n",
    "        return res[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:\n",
    "\n",
    "        # A.length <= 500\n",
    "        # B.length <= 500\n",
    "        # Time complexity: O(MN)\n",
    "        # Space complexity: O(N)\n",
    "\n",
    "        l_a, l_b = len(A), len(B)\n",
    "        dp = [0] * (l_b + 1)\n",
    "        for i in range(1, l_a + 1):\n",
    "            pre = dp[0]\n",
    "            for j in range(1, l_b + 1):\n",
    "                tmp = dp[j]\n",
    "                if A[i - 1] == B[j - 1]:\n",
    "                    dp[j] = pre + 1\n",
    "                else:\n",
    "                    dp[j] = max(dp[j - 1], dp[j])\n",
    "                pre = tmp\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:\n",
    "        #最长公共子串\n",
    "        l1, l2 = len(A), len(B)\n",
    "        dp = [[0 for _ in range(l2+1)] for _ in range(l1+1)]\n",
    "        \n",
    "        for i in range(1, l1+1):\n",
    "            for j in range(1, l2+1):\n",
    "                dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "                if A[i-1] == B[j-1]:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)\n",
    "                    \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:\n",
    "        '''\n",
    "        possible_line = []\n",
    "        for i in range(len(A)):\n",
    "            for j in range(len(B)):\n",
    "                if A[i] == B[j]:\n",
    "                    possible_line.append([i,j])\n",
    "        possible_line.sort(key=lambda x: (x[0], -x[1]))\n",
    "        arr = []\n",
    "        for each in possible_line:\n",
    "            pos = bisect.bisect_left(arr, each[1])\n",
    "            if pos == len(arr):\n",
    "                arr.append(each[1])\n",
    "            else:\n",
    "                arr[pos] = each[1]\n",
    "        return len(arr)\n",
    "        '''\n",
    "\n",
    "        arr = []\n",
    "        for i in range(len(A)):\n",
    "            j = len(B) - 1\n",
    "            while j >= 0:\n",
    "                if A[i] == B[j]:\n",
    "                    pos = bisect.bisect_left(arr, j)\n",
    "                    if pos == len(arr):\n",
    "                        arr.append(j)\n",
    "                    else:\n",
    "                        arr[pos] = j\n",
    "                j -= 1\n",
    "        return len(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:\n",
    "        # 动态gay 化\n",
    "        # 同 那个最长公共子序列\n",
    "        m, n = len(A), len(B)\n",
    "        dp = [[0 for i in range(n + 1)] for j in range(m + 1)]\n",
    "        #base case\n",
    "       \n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if A[i-1] == B[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:\n",
    "        dp = [[1 for _ in range(len(A))]for _ in range(len(B))]\n",
    "        #初始化dp[:][0]\n",
    "        for i in range(len(A)):\n",
    "            if(A[i]!=B[0]):\n",
    "                dp[0][i]=0\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        for i in range(len(B)):\n",
    "            if(B[i]!=A[0]):\n",
    "                dp[i][0]=0\n",
    "            else:\n",
    "                break\n",
    "        for i in range(1, len(B)):\n",
    "            for j in range(1, len(A)):\n",
    "                if B[i] == A[j]:\n",
    "                    #if i==0 and j==0:\n",
    "                    #    dp[i][j] = 1\n",
    "                    #else:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:\n",
    "        m, n = len(A), len(B)\n",
    "        dp = [[0] * (n+1) for _ in range(m+1)]\n",
    "        print(dp)\n",
    "        ans = 0\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if A[i-1] == B[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                    ans = max(ans, dp[i][j])\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:\n",
    "        # 最长公共子序列\n",
    "        nums = set(A) & set(B)\n",
    "        A, B = [i for i in A if i in nums], [i for i in B if i in nums]\n",
    "        nA = len(A)\n",
    "        nB = len(B)\n",
    "        dp = [[0 for i in range(nB+1)] for i in range(nA+1)]\n",
    "       \n",
    "        for i in range(1,nA+1):\n",
    "            for j in range(1,nB+1):\n",
    "                if A[i-1] == B[j-1]:\n",
    "                    print(i,j)\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        return dp[nA][nB]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        dp1 = [0] * (n + 1)\n",
    "        dp2 = [0] * (n + 1)\n",
    "\n",
    "        for i, num1 in enumerate(nums1):\n",
    "            dp1 = [0] * (n + 1)\n",
    "            dp1 = copy.deepcopy(dp2)\n",
    "            for j, num2 in enumerate(nums2):\n",
    "                if num1 == num2:\n",
    "                    dp2[j + 1] = dp1[j] + 1\n",
    "                else:\n",
    "                    dp2[j + 1] = max(dp1[j + 1], dp2[j])\n",
    "        \n",
    "        return dp2[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        d =dict()\n",
    "        n1 = len(nums1)\n",
    "        n2 = len(nums2)\n",
    "        for i in range(n2):\n",
    "            if nums2[i] not in d:\n",
    "                d[nums2[i]] = [i]\n",
    "            else: d[nums2[i]].append(i)\n",
    "        ans = []\n",
    "        for i in range(n1):\n",
    "            if(nums1[i] in d):\n",
    "                for item in d[nums1[i]][::-1]:\n",
    "                    j = bisect.bisect(ans,item)\n",
    "                    while(j>0 and ans[j-1]==item):\n",
    "                        j-=1\n",
    "                    if(j==len(ans)): ans.append(item)\n",
    "                    else: ans[j]=item\n",
    "        return len(ans) \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef maxUncrossedLines(self, nums1, nums2):\n",
    "\t\tmap0 = {}\n",
    "\t\tfor i, num in enumerate(nums2):\n",
    "\t\t\tif num in map0:\n",
    "\t\t\t\tmap0[num].append(i)\n",
    "\t\t\telse:\n",
    "\t\t\t\tmap0[num] = [i]\n",
    "\t\tlast = {0: -1}\n",
    "\t\tans = 0\n",
    "\t\tfor i, num in enumerate(nums1):\n",
    "\t\t\tcur = {0: -1}\n",
    "\t\t\tfor key in last:\n",
    "\t\t\t\tidx = self.find(map0.get(num, []), last[key])\n",
    "\t\t\t\tif idx == -1:\n",
    "\t\t\t\t\tbreak\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tcur[key + 1] = idx\n",
    "\t\t\tans = max(ans, max(cur.keys()))\n",
    "\t\t\tfor key in cur:\n",
    "\t\t\t\tlast[key] = min(last.get(key, len(nums2)), cur[key])\n",
    "\t\treturn ans\n",
    "\t\n",
    "\tdef find(self, nums, idx):\n",
    "\t\tif len(nums) == 0 or idx >= nums[-1]:\n",
    "\t\t\treturn -1\n",
    "\t\treturn nums[self.bs(nums, idx, 0, len(nums))]\n",
    "\t\n",
    "\tdef bs(self, nums, x, l, r):\n",
    "\t\tif l == r:\n",
    "\t\t\treturn r\n",
    "\t\tm = (l + r) >> 1\n",
    "\t\tif nums[m] > x:\n",
    "\t\t\treturn self.bs(nums, x, l, m)\n",
    "\t\telse:\n",
    "\t\t\treturn self.bs(nums, x, m + 1, r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        d = [[0] * (n2 + 1) for _ in range(n1+1)]\n",
    "        for i in range(1, n1+1):\n",
    "            for j in range(1, n2+1):\n",
    "                if nums1[i-1] == nums2[j-1]:\n",
    "                    d[i][j] = d[i-1][j-1] + 1\n",
    "                else:\n",
    "                    d[i][j] = max(d[i-1][j], d[i][j-1], d[i-1][j-1])\n",
    "        return d[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dp = [[0] * (len(nums1) + 1)for i in range(len(nums2) + 1)]\n",
    "        for i in range(1,len(nums2) + 1):\n",
    "            for j in range(1,len(nums1) + 1):\n",
    "                if(nums1[j-1] == nums2[i-1]):\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j-1],dp[i-1][j])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        m = len(nums2)\n",
    "\n",
    "        dp = [[0] * (n+1) for _ in range(m+1)]\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if nums1[j-1] == nums2[i-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        temp = [0] * len(nums2)\n",
    "        for i in range(len(nums1)):\n",
    "            for j in reversed(range(len(nums2))):\n",
    "                if nums1[i] == nums2[j]:\n",
    "                    if j == 0:\n",
    "                        temp[0] = 1\n",
    "                    else:\n",
    "                        temp[j] = max(max(temp[: j]) + 1, temp[j])\n",
    "        return max(temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1) + 1\n",
    "        m = len(nums2) + 1\n",
    "        dp = [0] * m\n",
    "        for x in nums1:\n",
    "            pre = 0\n",
    "            for i in range(1, m):\n",
    "                cur = dp[i]\n",
    "                if nums2[i - 1] == x:\n",
    "                    dp[i] = pre + 1\n",
    "                elif dp[i - 1] > dp[i]:\n",
    "                    dp[i] = dp[i - 1]\n",
    "                pre = cur\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dp = [[0]*(len(nums2)+1) for _ in range(len(nums1)+1)]\n",
    "\n",
    "        for i in range(1, len(nums1)+1):\n",
    "            for j in range(1, len(nums2)+1):\n",
    "                if nums1[i-1] == nums2[j-1]:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+1)\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        \n",
    "        return max(map(max, dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dp = [[0]*(len(nums2)+1)  for _ in range(len(nums1)+1)]\n",
    "        #  dp[i][j] 以 text1[i-1], text2[j-1] 最长的长度\n",
    "        for i in range(1, len(nums1)+1):\n",
    "            for j in range(1, len(nums2)+1):\n",
    "                if nums1[i-1] == nums2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        \n",
    "        #  dp[i][j]  nums1前i个数，nums2前j个数 所能够绘制的最大连线数\n",
    "\n",
    "        dp = [[0] * (len(nums2) + 1) for _ in range(0, len(nums1) + 1)]\n",
    "\n",
    "        for i in range(1, len(nums1) + 1):\n",
    "            for j in range(1, len(nums2) + 1):\n",
    "                if nums1[i -1] == nums2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dp = [[0 for _ in range(len(nums2)+1)] for _ in range(len(nums1)+1)]\n",
    "        dp2 = [[0 for _ in range(len(nums2)+1)] for _ in range(len(nums1)+1)]\n",
    "        for i in range(1,len(nums1)+1):\n",
    "            for j in range(1,len(nums2)+1):\n",
    "                if nums1[i-1] == nums2[j-1]:\n",
    "                    if i == j:\n",
    "                        dp[i][j] = dp[i-1][j-1] + 1\n",
    "                        dp2[i][j] = 0\n",
    "                    if i > j and dp2[i-1][j-1] >= 0:\n",
    "                        dp[i][j] = dp[i-1][j-1] + 1\n",
    "                        dp2[i][j] = 1\n",
    "                    if i < j and dp2[i-1][j-1] <= 0:\n",
    "                        dp[i][j] = dp[i-1][j-1] + 1\n",
    "                        dp2[i][j] = -1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n",
    "                    dp2[i][j] = dp2[i-1][j-1]\n",
    "        return dp[-1][-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
